package leetcode_1301_1400;

import java.util.*;

public class LeeCode_1377 {
    public static void main(String[] args) {
//        System.out.println(frogPosition(7, new int[][]{{1, 2}, {1, 3}, {1, 7}, {2, 4}, {2, 6}, {3, 5}}, 2, 6));
        System.out.println(frogPosition(1, new int[][]{}, 1, 1));
    }
    static class Node{
        double p;
        int now;
        int pre;

        public Node(int now, int pre, double p) {
            this.p = p;
            this.now = now;
            this.pre = pre;
        }
    }
    private static double frogPosition(int n, int[][] edges, int t, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            if (map.containsKey(edge[0])){
                map.get(edge[0]).add(edge[1]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(edge[1]);
                map.put(edge[0], list);
            }
            if (map.containsKey(edge[1])){
                map.get(edge[1]).add(edge[0]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(edge[0]);
                map.put(edge[1], list);
            }
        }
        if (map.size() == 0){
            return target == 1 ? 1 : 0;
        }
        LinkedList<Node> list = new LinkedList<>();
        double p = (double) 1 / map.get(1).size();
        for (Integer next : map.get(1)) {
            list.addFirst(new Node(next, 1, p));
        }
        int time = 1;
        while (time < t){
            int size = list.size();
            for (int i = 0; i < size; i++) {
                Node node = list.pollFirst();
                List<Integer> ns = map.get(node.now);
                double np = node.p * ((double) 1 / (ns.size() - 1));
                if (ns.size() == 1){
                    list.addLast(node);
                    continue;
                }
                for (Integer next : ns) {
                    if (next == node.pre)
                        continue;
                    list.addLast(new Node(next, node.now, np));
                }
            }
            time++;
        }
        for (Node node : list) {
            if (node.now == target){
                return node.p;
            }
        }
        return 0;
    }
}
